在 Functional 資料結構中的資料分享

當資料為不可變的情況下，可以的話我們會希望能夠重用所有資料，盡量減少複製情況發生，就稱做 資料分享 (data sharing)，

假設我們想幫 List 在最前面的地方加上節點 a，我們可以用以下方式重用已在記憶體的資料，而不是複製它，

以相同邏輯脈絡來看，當我們想在 List 中刪除頭節點，實際上也只是把 tail 的參照回傳回去而已，a 的資料還是存在在記憶體中，直到被記憶體回收機制回收。

Exercise D4-1

實做 setHead function，它能讓我們更新頭節點的值，需考量到輸入可能是空 List 的情況。

def setHead[A](l: List[A], head: A): List[A] 

Exercise D4-2

實做 drop function，它能讓我們從 List 中移除前 n 個節點。

  def drop[A](l: List[A], n: Int): List[A]

讓我們來看另一個使用資料分享的案例 append，該 function 能新增 a2 到 a1 後面，

  def append[A](a1: List[A], a2: List[A]): List[A] =
    a1 match
      case Nil => a2
      case Cons(h, t) => Cons(h, append(t, a2))
      

此 append function 的時間、空間複雜度是以 a1 為主，因為我們只複製了 a1，而欲新增的 a2 我們直接使用，不做任何複製，

想像一下若要 append 的結構是 array，你務必要在記憶體 new 包含 a1, a2 長度的 array 空間，然後在把 a1, a2 元素複製過去才行。

List 的遞迴

我們回頭看一下 昨天 Day 3 的 List companion object 中有定義的 2 個 function，

  def sum(ints: List[Int]): Int = ints match // 使用 pattern match 來加總 List 中的元素
    case Nil => 0 // 若欲加總的是空 list 則給它 0
    case Cons(x,xs) => x + sum(xs) // 把目前的 `x` 加上其他剩下值的加總

  def product(doubles: List[Double]): Double = doubles match
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)

我們可以觀察到，這 2 個 function 都是基於一個初始值，然後使用遞迴的方式遍歷所有元素，在依 * 或 + 去計算結果；所以基於 DRY (Don't Repeat Yourself) 原則，我們可以抽象成這樣，

  def foldRight[A, B](as: List[A], z: B, f: (A, B) => B): B = as match
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z, f))

z 是初始值，f 是我們可自定義的 high-order function，我們一樣使用遞迴去遍歷所有元素，然後將之前計算的結果，以及目前的值當做參數傳入給 f，並且使用多型 A, B 來讓此 function 更萬用，

high-order function 是用來定義一個 function (a) 可以把另一個 function (b) 當做參數傳遞過去，

例如 def filter(f: Int => Boolean): Array[Int]，filter 能接受一個 function f 做為參數，f 的輸入是 Int，而輸出是 Boolean，

我們可以使用 filter 排除所有 Array 中不符合條件的值，所以我們就可以用這個 filter function 來排除 Array 中所有偶數（以下程式使用 Scala REPL 執行），

scala> val arr = Array(1,2,3)
val arr: Array[Int] = Array(1, 2, 3)


scala> arr.filter((x: Int) => x % 2 == 1)
Array(1, 3)

scala> arr.filter(x => x % 2 == 1)
Array(1, 3)

scala> arr.filter(_ % 2 == 1)
Array(1, 3)

high-order function 有多種寫法，上面 3 種都代表相同意思，若 function 定義單純，則可以使用 _ 代表由左到右的參數使用順序。

BTW Scala 3 跟 Scala 2 的 high-order function 沒有什麼差別就是了。

有了 foldRight 後，我們的 sum 和 product 就能改寫成以下這樣，

  def sum(ints: List[Int]): Int = foldRight(ints, 0, _ + _)
  def product(doubles: List[Double]): Double = foldRight(doubles, 1.0 , _ * _)

如果有點難懂，我們可以細部分解一下 sum(List(1, 2, 3)) 這個例子，

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, (x,y) => x + y)

1 + foldRight(Cons(2, Cons(3, Nil)), 0, (x,y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0, (x,y) => x + y))
1 + (2 + (3 + foldRight(Nil, 0, (x,y) => x + y)))
1 + (2 + (3 + (0)))

6

我們不需要宣告本地變數以及依告修改本地變數的值來計算結果，functional programming 下的許多操作都是用 pattern match 和 遞迴來實現。

Exercise D4-3

使用 foldRight 來實現 function length，它能計算 List 的長度。

def length[A](l: List[A]): Int 

還沒完明天繼續。

Day 4 - Exercise answer